๋ฌธ์
๋๋๊ณค ์ปค๋ธ๋ ๋ค์๊ณผ ๊ฐ์ ์ธ ๊ฐ์ง ์์ฑ์ผ๋ก ์ด๋ฃจ์ด์ ธ ์์ผ๋ฉฐ, ์ด์ฐจ์ ์ขํ ํ๋ฉด ์์์ ์ ์๋๋ค. ์ขํ ํ๋ฉด์ x์ถ์ โ ๋ฐฉํฅ, y์ถ์ โ ๋ฐฉํฅ์ด๋ค.
- ์์ ์
- ์์ ๋ฐฉํฅ
- ์ธ๋
0์ธ๋ ๋๋๊ณค ์ปค๋ธ๋ ์๋ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ ๊ธธ์ด๊ฐ 1์ธ ์ ๋ถ์ด๋ค. ์๋ ๊ทธ๋ฆผ์ (0, 0)์์ ์์ํ๊ณ , ์์ ๋ฐฉํฅ์ ์ค๋ฅธ์ชฝ์ธ 0์ธ๋ ๋๋๊ณค ์ปค๋ธ์ด๋ค.
1์ธ๋ ๋๋๊ณค ์ปค๋ธ๋ 0์ธ๋ ๋๋๊ณค ์ปค๋ธ๋ฅผ ๋ ์ ์ ๊ธฐ์ค์ผ๋ก ์๊ณ ๋ฐฉํฅ์ผ๋ก 90๋ ํ์ ์ํจ ๋ค์ 0์ธ๋ ๋๋๊ณค ์ปค๋ธ์ ๋ ์ ์ ๋ถ์ธ ๊ฒ์ด๋ค. ๋ ์ ์ด๋ ์์ ์ ์์ ์ ๋ถ์ ํ๊ณ ์ด๋ํ์ ๋, ๊ฐ์ฅ ๋จผ ๊ฑฐ๋ฆฌ์ ์๋ ์ ์ ์๋ฏธํ๋ค.
2์ธ๋ ๋๋๊ณค ์ปค๋ธ๋ 1์ธ๋๋ฅผ ๋ง๋ ๋ฐฉ๋ฒ์ ์ด์ฉํด์ ๋ง๋ค ์ ์๋ค. (ํ๋์ ์ ๋ถ์ ์๋ก ์ถ๊ฐ๋ ์ ๋ถ์ ๋ํ๋ธ๋ค)
3์ธ๋ ๋๋๊ณค ์ปค๋ธ๋ 2์ธ๋ ๋๋๊ณค ์ปค๋ธ๋ฅผ ์ด์ฉํด ๋ง๋ค ์ ์๋ค. ์๋ ๊ทธ๋ฆผ์ 3์ธ๋ ๋๋๊ณค ์ปค๋ธ์ด๋ค.
์ฆ, K(K > 1)์ธ๋ ๋๋๊ณค ์ปค๋ธ๋ K-1์ธ๋ ๋๋๊ณค ์ปค๋ธ๋ฅผ ๋ ์ ์ ๊ธฐ์ค์ผ๋ก 90๋ ์๊ณ ๋ฐฉํฅ ํ์ ์ํจ ๋ค์, ๊ทธ๊ฒ์ ๋ ์ ์ ๋ถ์ธ ๊ฒ์ด๋ค.
ํฌ๊ธฐ๊ฐ 100ร100์ธ ๊ฒฉ์ ์์ ๋๋๊ณค ์ปค๋ธ๊ฐ N๊ฐ ์๋ค. ์ด๋, ํฌ๊ธฐ๊ฐ 1ร1์ธ ์ ์ฌ๊ฐํ์ ๋ค ๊ผญ์ง์ ์ด ๋ชจ๋ ๋๋๊ณค ์ปค๋ธ์ ์ผ๋ถ์ธ ์ ์ฌ๊ฐํ์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ๊ฒฉ์์ ์ขํ๋ (x, y)๋ก ๋ํ๋ด๋ฉฐ, 0 โค x โค 100, 0 โค y โค 100๋ง ์ ํจํ ์ขํ์ด๋ค.
์ , ์ถ๋ ฅ
์ ๋ ฅ
- ์ฒซ์งธ ์ค์ ๋๋๊ณค ์ปค๋ธ์ ๊ฐ์ N(1 โค N โค 20)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์๋ ๋๋๊ณค ์ปค๋ธ์ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋ค. ๋๋๊ณค ์ปค๋ธ์ ์ ๋ณด๋ ๋ค ์ ์ x, y, d, g๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. x์ y๋ ๋๋๊ณค ์ปค๋ธ์ ์์ ์ , d๋ ์์ ๋ฐฉํฅ, g๋ ์ธ๋์ด๋ค. (0 โค x, y โค 100, 0 โค d โค 3, 0 โค g โค 10)
- ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ ๋๋๊ณค ์ปค๋ธ๋ ๊ฒฉ์ ๋ฐ์ผ๋ก ๋ฒ์ด๋์ง ์๋๋ค. ๋๋๊ณค ์ปค๋ธ๋ ์๋ก ๊ฒน์น ์ ์๋ค.
-
๋ฐฉํฅ์ 0, 1, 2, 3 ์ค ํ๋์ด๊ณ , ๋ค์์ ์๋ฏธํ๋ค.
- 0: x์ขํ๊ฐ ์ฆ๊ฐํ๋ ๋ฐฉํฅ (โ)
- 1: y์ขํ๊ฐ ๊ฐ์ํ๋ ๋ฐฉํฅ (โ)
- 2: x์ขํ๊ฐ ๊ฐ์ํ๋ ๋ฐฉํฅ (โ)
- 3: y์ขํ๊ฐ ์ฆ๊ฐํ๋ ๋ฐฉํฅ (โ)
์ถ๋ ฅ
- ์ฒซ์งธ ์ค์ ํฌ๊ธฐ๊ฐ 1ร1์ธ ์ ์ฌ๊ฐํ์ ๋ค ๊ผญ์ง์ ์ด ๋ชจ๋ ๋๋๊ณค ์ปค๋ธ์ ์ผ๋ถ์ธ ๊ฒ์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค.
๐ Logic
class DragonMap {
int[][] map = new int[101][101];
int[] rangeX = { 1, 0, -1, 0 };
int[] rangeY = { 0, -1, 0, 1 };
...
}
- ๋๋๊ณค ์ปค๋ธ๋ฅผ ๊ทธ๋ฆฌ๊ธฐ ์ํ
map๊ณผ ๋ฐฉํฅ์ ๋ฐ๋ฅธ ์ด๋์ ์ํด ์ฌ์ฉํ๋ ๋ฒ์ ์ ๋ณด๋ฅผ ์ ์ฅํ๋ ํด๋์ค
public void drawDragonCurves(int x, int y, int d, int g) {
List<Integer> dirList = new ArrayList<>();
dirList.add(d);
for (int i = 0; i < g; i++) {
for (int j = dirList.size() - 1; j >= 0; j--) {
dirList.add(getCountClockDir(dirList.get(j)));
}
}
map[x][y] = 1;
for (Integer dir : dirList) {
x += rangeX[dir];
y += rangeY[dir];
map[x][y] = 1;
}
}
- ๋ฆฌ์คํธ์ ๋ฐฉํฅ ์ ๋ณด๋ฅผ ์ ์ฅํ๊ณ , ๋ง์ง๋ง์ ์ ์ฅํ ๋ฐฉํฅ ์ ๋ณด๋ถํฐ ์ฐจ๋ก๋ก ๋ฐ์๊ณ ๋ฐฉํฅ์ผ๋ก ๋๋ฆฐ ๋ฐฉํฅ ์ ๋ณด๋ฅผ ์ ์ฅํ๋ค.
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class DragonMap {
int[][] map = new int[101][101];
int[] rangeX = { 1, 0, -1, 0 };
int[] rangeY = { 0, -1, 0, 1 };
public void drawDragonCurves(int x, int y, int d, int g) {
List<Integer> dirList = new ArrayList<>();
dirList.add(d);
for (int i = 0; i < g; i++) {
for (int j = dirList.size() - 1; j >= 0; j--) {
dirList.add(getCountClockDir(dirList.get(j)));
}
}
map[x][y] = 1;
for (Integer dir : dirList) {
x += rangeX[dir];
y += rangeY[dir];
map[x][y] = 1;
}
}
public int countSquares() {
int counts = 0;
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
if (map[i][j] == 1 && map[i][j + 1] == 1 && map[i + 1][j] == 1 && map[i + 1][j + 1] == 1) {
counts++;
}
}
}
return counts;
}
private int getCountClockDir(int dir) {
return (dir + 1) % 4;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
DragonMap dragons = new DragonMap();
for (int i = 0; i < N; i++) {
int[] info = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
dragons.drawDragonCurves(info[0], info[1], info[2], info[3]);
}
br.close();
System.out.println(dragons.countSquares());
}
}
โ๏ธ Review
- ๋งค ์ธ๋๋ง๋ค ๋ฐฉํฅ์ด ๋ฐ๋๋ ๊ฒ์ ๋ํด, ์ด๋ฅผ ๋ฆฌ์คํธ์ ์ ์ฅํ๊ณ ๊ณ์ ์
๋ฐ์ดํธํด์ฃผ๋ ๋ฐฉ์์ ์๊ฐํ์ง๋ง, ์์ธ์ง ๋ฆฌ์คํธ๋ ํ์ฒ๋ผ
push,pop์ ํด์ผ ํ๋๊น ๋นํจ์จ์ ์ด์ง ์๋ ... ํ๋ ์๊ฐ์ ์ฌ๋ก์กํ ํผ์ ๊ฝ ๋งํ๋ฒ๋ ธ๋ค. - ๋ค๋ฅธ ๋ฐฉ๋ฒ์ ๋ญ๊ฐ ์๋ ์ถ์ด ํ ๋ธ๋ก๊ทธ๋ฅผ ๋ดค๋๋ฐ, ์๊ฐํ ๊ทธ๋๋ก๋ฅผ ๊ตฌํํ ๊ธ์ ๋ฐ๊ฒฌํด์ ๋์ ๋ฌด์งํจ์ ๊นจ๋ฌ์๋ค.
๐ ์ถ์ฒ
- Baekjoon : https://www.acmicpc.net/problem/15685
- 15685